package com.mgq.algorithm.link;

/**
 * @author MaGuangQi
 * 21题
 * 合并2个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
 * 比如 1,3,4
 * 1,2,3
 * 合并完是1,1,2,3,3,4
 * @date 2021-12-30 10:54
 **/
public class MergeTwoSortedLists_21
{
    public static void main(String[] args) {

    }

    /**
     * 思路:
     * 指定一个dummy节点.
     * pre指针,首先指向dummy节点.
     * l1和l2是2个指针,分别指向链表1和链表2
     * l1小于等于l2的值时,l1移动.pre指向l1
     * pre向前移动
     * 最后剩余的要么是list1,要么是list2
     * 时间复杂度O(M+N) 2个链表都循环了一遍
     * 空间复杂度O(1)
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return list1;
        }
        //保留dummy,留着返回
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                //pre指向list1
                pre.next=list1;
                //list1移动
                list1=list1.next;
            }else {
                pre.next=list2;
                list2=list2.next;
            }
            //注意:pre需要移动
            pre=pre.next;
        }
        //最后到最后时,剩余一个节点,不是list1就是list2
        pre.next=list1==null?list2:list1;
        return dummy.next;
    }

    /**
     * 递归解法
     * 每次返回串联后的结果
     * 然后递归地决定下一个添加到结果里的节点
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        //终止条件
        if (list1 == null) {
            //把list2剩余的返回
            return list2;
        }
        if (list2 == null) {
            //把list1剩余的返回
            return list1;
        }
        if (list1.val <= list2.val) {
            //list1指向list1.next和list2 的合并结果
            list1.next = mergeTwoLists2(list1.next, list2);
            return list1;
        } else {
            //list2指向list2.next和list1 的合并结果
            list2.next = mergeTwoLists2(list1, list2.next);
            return list2;
        }

    }
}
